//
//  BasicDataStruct.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/5/8.
//  Copyright © 2020 WangYonghe. All rights reserved.
//

import UIKit

class BasicDataStruct: NSObject {

}


//链表的节点
public class ListNode: NSObject{
    public var val: Int
    public var next: ListNode?
    
    public init(_ val: Int){
        self.val = val
        self.next = nil
    }
}




//栈结构
public class Stack: NSObject{
    public var stackSource: Array<Any> = []
    public var size:Int{
        return stackSource.count
    }
    public var isEmpty: Bool{
        return stackSource.count == 0
    }
    
    public func push(elememt: stackElement){
        stackSource.append(elememt)
    }
    
    public func pop(){
        if isEmpty == false {
            stackSource.removeLast()
        }else{
            isValidStackOper = false
        }
    }
    
    public var isValidStackOper: Bool = true
    
}
//栈元素
public class stackElement{
    public var eleValue: Int = 10
    public var eleStringValue: String? = ""
    
    public init(str:String){
        self.eleStringValue = str
    }
}



//二叉树
public class TreeNode{
    public var val: Int = 0
    public var left: TreeNode?
    public var right: TreeNode?
    
    public init(_ val: Int){
        self.val = val
        self.left = nil
        self.right = nil
    }
    
    //计算树的最大深度
    func maxDepth(_ root: TreeNode?)->Int{
        guard root != nil else {
            return 0
        }
        return max(maxDepth(root!.left),maxDepth(root!.right)) + 1
    }
    
    //是否是二叉查找树
    func isValidSeachTree(root: TreeNode)-> Bool{
        return help(node: root, min: nil, max: nil)
    }
    func help(node:TreeNode?, min :Int?, max :Int?) -> Bool{
        guard node != nil else {
            return true
        }
        if min != nil && node!.val < min! {
            return false
        }
        if max != nil && node!.val > max! {
            return false
        }
        return help(node: node?.left, min: min, max: node?.val) && help(node: node?.right, min: node?.val, max: max)
    }
    
    //二叉树的遍历
    //递归实现二叉树遍历
    func recuTraersal(root: TreeNode!){
        guard root != nil else {
            return
        }
        //前、中、后遍历只需改变一下三行代码的顺序
        print("\(root.val) ")
        recuTraersal(root: root.left)
        recuTraersal(root: root.right)
    }
    
    //满遍历
//    func fullTraverseTree(_ rootNode:TreeNode?){
//        if rootNode == nil {
//            //null
//            print("null")
//        }else{
//            print("\(rootNode!.val)")
//            self.fullTraverseTree(rootNode!.left)
//            self.fullTraverseTree(rootNode!.right)
//        }
//    }
    
    //用栈实现前序遍历
    func preorderTraversal(root: TreeNode?) -> [Int]{
        var res = [Int]()
        var stack = [TreeNode]()
        var node = root

        while !stack.isEmpty || node != nil {
            if node != nil {
                res.append(node!.val)
                stack.append(node!)
                node = node!.left
            }else {
                node = stack.removeLast().right
            }
        }
        return res
    }

    //用栈实现中序遍历
    func InorderTraversal(root: TreeNode?) -> [Int]{
        var res = [Int]()
        var stack = [TreeNode]()
        var node = root
        
        while !stack.isEmpty || node != nil {
            while node != nil {
                stack.append(node!)
                node = node?.left
            }
            node = stack.popLast()
            res.append(node!.val)
            node = node?.right
        }
        return res
    }
    
    //用栈实现后序遍历
    /*
     从根节点开始依次迭代，弹出栈顶元素输出到输出列表中，然后依次压入它的所有孩子节点，按照从上到下、从左至右的顺序依次压入栈中。

     因为深度优先搜索后序遍历的顺序是从下到上、从左至右，所以需要将输出列表逆序输出。
     */
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        guard root != nil else {
            return []
        }
        
        var res = [Int]()
        var stack:Array<TreeNode> = [root!]
        
        while !stack.isEmpty {
            let node = stack.removeLast()
            res.append(node.val)
            if node.left != nil {
                stack.append(node.left!)
            }
            if node.right != nil {
                stack.append(node.right!)
            }
        }
        return res.reversed()
    }
    
    //二叉树倒置 ---递归
    func MirroTree(root: TreeNode?){
        guard root != nil else {
            return
        }
        if root?.left == nil && root?.right == nil {
            return
        }
        let tempNode:TreeNode = root!.left!
        root?.left = root?.right
        root?.right = tempNode
        MirroTree(root: root?.left)
        MirroTree(root: root?.right)
    }
    //二叉树倒置 ---栈辅助
    func MirroTreeStack(_ root: TreeNode?) -> TreeNode? {
        guard root != nil else {
            return nil
        }
        
        var stack:Array<TreeNode> = [root!]

        while !stack.isEmpty {
            let node = stack.popLast()
            if node?.left != nil {
                stack.append(node!.left!)
            }
            if node?.right != nil{
                stack.append(node!.right!)
            }
            let tmp = node?.left
            node?.left = node?.right
            node?.right = tmp
        }
        return root
    }
}
